package org.example.Backtracking_algorithm;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Split_palindrome_string {
    public static LinkedList<String> value = new LinkedList<>();
    public static ArrayList<List<String>> result = new ArrayList<>();
    public static void main(String[] args) {
        //分割回文串

        //给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
        //回文串 是正着读和反着读都一样的字符串。
        partition("aab");
        prin();
    }
    public static List<List<String>> partition(String s) {
        get(s,0);
        return result;
    }
    public static void get(String s,int index){
        if (index==s.length()){
            result.add(new ArrayList<>(value));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (isRound(s,index,i)) {
                String str = s.substring(index, i + 1);
                value.add(str);
            }else{
                continue;
            }
            get(s,i+1);
            value.removeLast();
        }
    }
    public static boolean isRound(String s,int index,int k){
        for (int i = index,j = k; i <= j; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    public static void prin(){
        for (List<String> list : result) {
            System.out.print("[ ");
            for (String s : list) {
                System.out.print(s+" ");
            }
            System.out.print(" ]");
        }
        System.out.println();
    }
}
